/**
 * Created by clq on 2019/2/20.
 */
public class merge {
    public static void main(String[] args) {
        int arr[] = {34,2,24,2342,1324234,5,22,4325,234,2,24,2342,1324234,0};
        sort(arr);
        for(int i : arr) {
            System.out.println(i);
        }
    }

    public static void sort(int arr[]) {
        int temp[] = new int[arr.length];
        sort(arr, 0, arr.length-1, temp);
    }

    public static void sort(int arr[], int left, int right, int temp[]) {
        int mid = (left + right)/2;
        if(left < right) {
            sort(arr, left, mid, temp);
            sort(arr, mid+1, right, temp);
            merge(arr, left, mid, right, temp);
        }

    }

    public static void merge(int arr[], int left, int mid, int right, int temp[]) {
        int i = left;
        int j = mid+1;
        int t = 0;

        while (i<=mid && j<=right){
            if(arr[i] < arr[j]){
                temp[t++] = arr[i++];
            }else {
                temp[t++] = arr[j++];
            }
        }

        while (i<=mid) {
            temp[t++] = arr[i++];
        }

        while (j<=right) {
            temp[t++] = arr[j++];
        }

        t = 0;
        while (left <= right) {
            arr[left++] = temp[t++];
        }
    }
}
